1. Field of the Invention
The present invention relates to an image coding apparatus and method for compressing an image by wavelet transform and entropy coding as in JPEG-2000 for example, a program for allowing a computer to perform image coding, and a recording medium having the program recorded therein.
This application claims the priority of the Japanese Patent Application No. 2002-236620 filed on Aug. 14, 2002, the entirety of which is incorporated by reference herein.
2. Description of the Related Art
One of the typical image compression standards is JPEG (Joint Photographic Experts Group) standardized by the ISO (International Standards Organization). This is well known for assuring quality coding and decoding of an image and coded image, respectively, when comparatively many bits are assigned to the image using the discrete cosine transform (DCT). However, when the number of coding bits is reduced to more than a certain extent, the block skew peculiar to DCT will become noticeable and image degradation will also be noticeable subjectively.
Recently, there have actively been studied the techniques of dividing an image by a filter, called “filter bank”, formed from a combination of a high-pass filter and low-pass filter into a plurality of frequency bands and coding the image with respect to each divided band. Of these techniques, the wavelet transform coding is regarded as a new most promising technique which can take the place of DCT because it is free from the noticeable block skew caused by DCT when an image is highly compressed.
For example, JPEG-2000 internationally standardized completely in January, 2001 adopts a combination of the wavelet transform and high-efficiency entropy coding (bit modeling in units of a bit plane and arithmetic coding) and has been considerably improved in efficiency of coding as compared with the conventional JPEG.
In an image encoder to compress an image by coding as in JPEG-2000, an input image is divided into a plurality of subbands by making wavelet transform of the image, and a wavelet transform coefficient is quantized for each of the subbands. Then, a quantization coefficient thus determined for each subband is divided into coding blocks, namely, units of entropy coding, each having a predetermined size of about 64×64, for example, and the quantization coefficient in units of a coding block is modeled by coefficient bit.
The coefficient bit modeling will be explained in detail below. It should be noted that the coefficient bit modeling will be described taking the entropy coding called “embedded coding with optimized truncation (EBCOT)” defined in JPEG-2000 as an example. The “EBCOT” is referred in detail to the publication “ISO/IEC 15444-1, Information Technology—JPEG 2000, Part 1: Core coding system” etc.
Prior to the explanation of EBCOT, the concept of a bit plane will first be explained with reference to FIG. 1. FIG. 1(A) shows a quantization coefficient assumed to include sixteen coefficients (four by four). As shown, one of the sixteen coefficients has a largest absolute value of 13 whose binary notation is “1101”. Therefore, the bit plane defined by absolute values of the coefficients is a layer of four bit planes as shown in FIG. 1(B). It should be noted that all elements (sample points) in each bit plane take a value “0” or “1”. On the other hand, all the quantization coefficients take a value “0” or a positive value except for one which takes a value “−6”. Therefore, a code bit plane is as shown in FIG. 1(C).
EBCOT is a means for coding each block having a predetermined size while measuring the statistic amount of coefficient bit data in the block. By this means, the coefficient bit data is entropy-coded in code blocks. The code block is coded independently for each bit plane in a direction from the most significant bit (MSB) toward least significant bit (LSB). Also, the code block has a size which is a two's power from 4 to 256, normally, any of 32×32, 64×64, 128×32, etc. The quantization coefficient is represented by a signed binary number of n bits of which bit 0 to bit (n−2) indicate LSB to MSB, respectively. It should be noted that a remaining one bit indicates a sign. The code block is processed by three kinds of coding passes (a) to (c) as follows starting with an MSB-side bit plane.
(a) Significance Propagation pass
(b) Magnitude Refinement pass
(c) Cleanup pass
The three coding passes are used in an order shown in FIG. 2. As shown in FIG. 2, a bit plane (n−2) (MSB) is first processed by the “Cleanup pass” (will be referred to as “CU pass” wherever appropriate hereunder). Next, each bit plane is processed by the “Significance Propagation pass” (will be referred to as “SP pass” wherever appropriate hereunder) and “Magnitude Refinement pass” (will be referred to as “MR pass” wherever appropriate hereunder) and CU pass sequentially in this order toward LSB.
Actually, however, it is described in the header in which bit plane counted from MSB “1” appears first, not to code any bit plane of all “0”. By coding a bit plane with repetition of the three kinds of coding passes in the above order and exiting the coding when up to an arbitrary coding pass of an arbitrary bit plane is completed, it is possible to make a tradeoff between the code amount and image quality, that is, it is possible to control the rate.
The coefficient bit data is scanned as will be described herebelow with reference to FIG. 3. The code block is divided into a stripe at every four sample points in height. The stripe width is equal to the width of the code block. The order of scanning is an order in which all sample points in one code block are scanned. In the code block, sample points are scanned from an upper stripe to a lower one. In each stripe, sample points are scanned from a left column to a right one. In each column, sample points are scanned from top to bottom. It should be noted that in each coding pass, all the sample points in the code block are processed in the order of scanning. The above-mentioned three coding passes will be described below.
(a) Significance Propagation (SP) Pass
In the SP pass to code a bit plane, coefficient bit data at “non-significant” sample points near “8” and of which at least one is “significant” are coded arithmetically. When the coded coefficient bit data is “1”, the signs, plus and minus, of the code are successively coded arithmetically.
The term “significant” used herein refers to a state the coder has for each of sample points. The initial value of “significant” is “0” which means “non-significant”, and when “1” is coded for the sample point, the initial value changes to “1” which means “significant” and it will always stay at “1”. Therefore, the “significant” can be said to be a flag indicating whether effective-digit information has already been coded. When an SP pass takes place in a bit plane, no SP pass will take place in any subsequent bit planes.
(b) Magnitude Refinement (MR) Pass
In the MR pass to code a bit plane, coefficient bit data at a “significant” sample point, not processed by the SP pass which codes the bit plane, is coded arithmetically.
(c) Cleanup (CU) Pass
In the CU pass to code a bit plane, coefficient bit data at a “non-significant” sample point, not processed by the SP plane which codes the bit plane, is coded arithmetically. When the coded coefficient bit data is “1”, the signs, plus and minus, of the code are successively coded arithmetically.
Note that in the arithmetic coding in the above three coding passes, the context at a sample point is selected by selectively using Zero Coding (ZC), Run-length Coding (RLC), Sign Coding (SC) or Magnitude Refinement (MR) as the case may be. Then, a context selected by arithmetic coding called “MQ coding” is coded. The MQ coding is a binary arithmetic coding of a learning type defined in JBIG2. The MQ coding is referred to the publication “ISO/IEC FDIS 14492, “Lossy/Lossless Coding of Bi-level Images”, March 2000” and the like, for example. In JPEG-2000, there is defined a total of 19 kinds of contexts for all coding passes.
In the image coder to compress by coding according to JPEG-2000 as above, a quantization coefficient of each code block is decomposed into bit planes, each of the bit planes is decomposed into three coding passes, and coefficient bit data is generated for each of the coding passes. Then, the coefficient bit data for each coding pass is coded arithmetically.
The MR pass is intended for arithmetic coding of coefficient bit data which is made “significant” by the CU pass or SP pass in any other bit plane, and the CU pass is intended for arithmetic coding of “non-significant” coefficient bit data not processed by the SP pass. Therefore, it is believed that if the SP pass can be done at a higher speed, code blocks can be processed by the three cording passes at a higher speed.
In the SP pass, coefficient bit data at “non-significant” sample points near “8” and of which at least one is “significant” are coded arithmetically as above. When the coded coefficient bit data is “1”, the state of the sample point changes from “non-significant” to “significant”. Conventionally, since a sample point to be processed by the SP pass will take place due to the state change as the case may be, it is not possible to selectively code only sample points which have to be processed by the SP pass.
This problem will be described simply below with reference to FIG. 4. It should be noted that in FIG. 4, there is shown an assumed bit plane consisting of a total of sixteen (four by four) coefficient bit data, and an expediential number is appended at upper left in each sample point to indicate the position of the sample point. In FIG. 4, the thick-line frame indicates a “significant” sample point. As shown in FIG. 4(A), since only the tenth sample point is “significant” at a step of starting a bit plate coding, eight samples, that is, fifth to seventh, ninth, eleventh, thirteenth to fifteenth, are to be processed by the SP pass. Since coefficient bit data at the seventh sample point is “1”, however, this sample point will be changed by the SP pass to the state “significant” as shown in FIG. 4(B). Thus, the eighth and twelfth samples will be new sample to be processed by the SP pass.
On this account, a sample point is judged to be or not to be a one to be processed by the SP pass in the order of scanning. When the sample point is determined to be processed by the SP pass, it is processed by the SP pass. If the sample point is not any one to be processed so, a next sample point is judged. Such operations are repeatedly done. Thus, a number of operation cycles for sample points included in a bit plate and which are to be processed by the SP pass within a bit plane cannot complete the SP pass but a number of operation cycles for all the sample points is required.